__author__ = 'st316'
'''
Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?
'''


#Definition for a  binary tree node
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def __repr__(self):
        return self.val


class Solution:
    # @param root, a tree node
    # @return a list of integers
    def postorderTraversal(self, root):
        if not root:
            return []
        lst = []

        stack = []
        stack.append(root)

        prev = None
        while stack:
            curr = stack[-1]

            # go down the tree.
            #check if current node is leaf, if so, process it and pop stack,
            #otherwise, keep going down
            if not prev or prev.left == curr or prev.right == curr:
                #prev == null is the situation for the root node
                if curr.left:
                    stack.append(curr.left)
                elif curr.right:
                    stack.append(curr.right)
                else:
                    stack.pop()
                    lst.append(curr.val)

            #go up the tree from left node
            #need to check if there is a right child
            #if yes, push it to stack
            #otherwise, process parent and pop stack
            elif curr.left == prev:
                if curr.right:
                    stack.append(curr.right)
                else:
                    stack.pop()
                    lst.append(curr.val)

            #go up the tree from right node
            #after coming back from right node, process parent node and pop stack.
            elif curr.right == prev:
                stack.pop()
                lst.append(curr.val)

            prev = curr
        return lst

    # @param root, a tree node
    # @return a list of integers
    def postorderTraversalX(self, root):
        l = []
        if root:
            l.extend(self.postorderTraversal(root.left))
            l.extend(self.postorderTraversal(root.right))
            l.append(root.val)
        return l


if __name__ == '__main__':
    s = Solution()
    root = TreeNode(1)
    root.right = TreeNode(2)
    root.right.left = TreeNode(3)
    print s.postorderTraversal(root)